1. Field of the Invention
The present invention generally relates to Content Addressable Memories (CAMs), and particularly relates to aborting CAM search operations.
2. Relevant Background
Content Addressable Memories (CAMs) are used to implement search-intensive tasks such as packet forwarding and classification in network routers, cache lookups and address translations in microprocessors, data coding/decoding, image coding, data compression/decompression, database acceleration, neural networking, etc. Conventional CAMs have a table of stored data arranged in groups, e.g., rows of data words. Each group comprises a plurality of CAM cells for storing data. CAM cells may be binary (store binary data) or ternary (store binary data or a ‘don't care’ state). During a CAM search operation, each match line is pre-charged to a logic high value, i.e., a voltage level that represents a logic one. A search field is then input to the CAM and broadcast onto search lines to the table of stored data. A match line coupled to each group of CAM cells indicates whether the search field matches data stored by a particular group. For example, in the event of a mismatch, also referred to as a miss, the match lines associated with the group or groups that cause a mismatch are activated by being discharged. Conversely, the match lines associated with the group or groups that yield a match, also referred to as a hit, remain pre-charged. CAMs that use ternary cells may produce multiple matched results since the ‘don't care’ state may yield multiple matches.
Some conventional CAMs incorporate multiple levels of match lines to reduce the adverse effects associated with capacitive loading. In such multi-level CAMs, each grouping of CAM cells includes multiple local match lines where each local match line detects hit/miss results for a subset of the CAM cells forming a particular group. The local match lines serving a certain group of CAM cells are coupled to a global match line. A mismatch indicated by one or more local match lines is reflected by the corresponding global match line. As such, a global match line yields a miss if any one of its corresponding local match lines indicates a miss. Conversely, the global match line yields a hit if all of its corresponding local match lines indicate a hit. Depending on CAM size, one or more intermediary match line levels may be included between local match lines and a corresponding global match line to further reduce the adverse effects of capacitive loading.
In one application, CAMs are used to implement high-performance processor caches. A conventional processor cache comprises a CAM portion and a RAM portion. The CAM portion stores data used for address lookups. The RAM portion stores data associated with the address data stored in the CAM. During a lookup portion of a processor cache access, the CAM is searched to determine whether an address of interest is stored in the CAM. If the CAM lookup yields a hit, the matching address is supplied to the RAM during a read portion of the cache access. The RAM provides data corresponding to the matched address during the read portion of the processor cache access.
Conventional processor cache access operations require multiple cycles, e.g., to identify matching addresses stored in a CAM and to read the corresponding data from a RAM. To prevent CAM search results from being lost during a multi-cycle cache access, a holding register stores CAM lookup results for subsequent use by a RAM. Conventional holding registers are formed from either static or monotonic storage devices. Static storage devices, e.g., static Complimentary Metal Oxide Semiconductor (CMOS) latches, have an output node that switches either high or low in response to a clock signal input. Conversely, monotonic storage devices, e.g., zero-catcher, one-catcher or jam latches, have an output skewed to favor a certain direction (high or low). Static storage devices capture input data, e.g., the state of a global CAM match line, in response to a clock signal input. However, the hit/miss state of a global match line is not determined until the end of the CAM access cycle, thus leaving little timing margin for the static CMOS storage device to capture the hit/miss state in response to a clock signal input.
Monotonic storage devices are skewed to favor one logic switching direction or another, but not both. For example, a zero-catcher latch captures a logic zero value without having to receive an active clock signal while a one-catcher latch captures a logic high value. Conversely, a zero-catcher latch captures a logic one value in response to an active clock signal while a one-catcher captures a logic zero value. As such, monotonic storage devices rapidly capture either a logic low state (zero-catcher) or logic high state (one-catcher) during a CAM evaluation period. For example, a zero-catcher latch captures a logic zero without regard to a clock signal input, thus near-instantaneously reacting to match line miss results. Likewise, a one-catcher latch captures a logic one near-instantaneously. Unlike static storage devices, monotonic storage devices almost immediately reflect the hit/miss state of a global match line regardless of a clock signal input, thus causing CAM search results previously stored in a corresponding holding register to be overwritten.